3.4 可靠数据传输的原理

本节的内容十分重要，请务必反复温习确保精通相关的知识。

我们已经无数次提到过了可靠数据传输，它在网络协议栈中的多层（如应用层、传输层与数据链路层）都很重要。可靠数据传输协议（Reliable Data Transfer Protocol） 的责任就是为上层的实体提供可靠数据传输的服务。具体而言，其为上层实体提供了一条可靠的数据传输信道，在该信道中传输的数据不会发生损坏、丢失或乱序问题。可靠数据传输协议仍然需要依赖其下层实体提供的服务，这种服务可能是可靠的，也可能是不可靠的。例如， TCP 即是在不可靠的 IP 协议之上实现的可靠数据传输协议。

为了理解可靠数据传输协议的工作原理，我们将从最理想的环境开始建构一个相对简单明了的协议，随后逐步去掉对于外界环境的假设，并为协议添加新的功能以适应更加不可靠的环境，直至接近现实情况。

下文将使用的相关记号与约定

在下面的叙述中，我们都假定数据传输是单向的，即数据总是从发送方传递到接收方。双向数据传输可以简单得看作两个方向相反的单向数据传输。然而，规定数据传输是单向的并不意味着信道只支持数据单向流动。毫无疑问，如果信道只允许数据单向流动，则发送方与接收方将无法交换控制报文，可靠数据传输也无从谈起。

Pasted image 20250422143515.png

如上图所示，我们使用如下几个字段来规定发送方与接收方进行的基本动作：

make_pkg 协议将数据封装为协议分组。
extract 协议将分组拆开获得载荷部分的有效数据。
rdt_send 上层实体调用发送方实体提供的服务接口，将需要发送的数据交付给协议实体。
deliver_data 上层实体调用接收方协议实体提供的服务接口，协议将收到的数据交付给上层。
udt_send 发送方协议实体调用下层服务接口，将分组放到信道（通常是不可靠的）上传输给接收方。
udt_rcv 接收方实体调用下层服务接口，从信道中收取分组。

我们使用 有限状态机（Finite State Machine，FSM） 来描述发送方与接收方的行为，其基本记号如下图：

Pasted image 20250422143539.png

Step 1. 经完全可靠信道的传输

显然本层协议基本不需要做任何事情，接收方只需要将上层传下来的数据封装成本层的协议分组后传递给下层信道即可，发送方收到数据后不需要做任何检验，拆下头部后就可以把载荷部分传递给上层。二者 FSM 如下：

Pasted image 20250422143600.png

Step 2. 经具有 bit 差错信道的传输

显然，解决报文受损最简单的方法是发送方重传分组，这被称作 自动重传请求（Automatic Repeat reQuest，ARQ）协议。在协议中，接收方可以通过返回 肯定请求（Positive Acknowledgment，ACK） 或 否定请求（Negative Acknowledgment，NAK） 通知发送方自己是否收到了无差错的分组。为了实现上述几点，我们需要实现以下几个功能：

差错检测，允许接收方确定收到的分组是否发生了 bit 差错（甚至可能直接修正这些错误）。
接收方反馈，允许发送方了解接收方情况。
重传，当接收方收到有差错的分组并反馈给接收方后，接收方可以重传该分组。

实现上述功能后，发送方与接收方的 FSM 如下：

Pasted image 20250422143736.png

如果不理解，打开这里我们做一些解释

我们在该状态机中模拟一下一次数据传输的过程：

上层实体向发送方协议实体交付要发送的数据，发送方实体计算出校验和后将这些数据连同校验和封装，然后发送。
接收方接收到分组，拆开得到载荷数据与校验和。接收方按照相同的方式对数据进行校验。如果校验通过，接收方将数据交付给上层并向发送方发送 ACK 分组。
发送方接收到接收方发送的 ACK 分组后继续进行下一个分组的发送。
如果校验没有通过，接收方丢弃该分组，并向发送方发送 NAK 分组。
发送方接收到接收方发送的 NAK 分组后，重新发送该分组，直至接收到 ACK 分组回到第 3 步。

该设计下，发送方只有当接收方接收到一个分组后才会发送下一个分组，这是一种 停等（Stop-and-wait） 协议。

然而，上述设计忽略了一个致命问题：ACK 与 NAK 报文在传输途中也会受损。解决这个问题的一个方法是当接收方接收到一个受损的反馈分组时，无论其原本是 ACK 还是 NAK，都进行一次重发，直到收到发送方发送的无差错的 ACK 分组。然而，在接收方这一边，当收到一个分组时，接收方无从确认发送方发送的到底是重传分组还是新的分组（协议实体显然不会去检查载荷部分的内容，这违反了网络传输的分层原则！）。而这时就需要引入 序号（sequence number） 来对发送的分组进行标识了。

由于原有的设计是一个停等协议，很明显信道中同时最多只会有两种分组在传输：重传的旧分组与新分组，因此只需要 1 bit 的序号进行标注即可。改良后双方的 FSM 如下：

Pasted image 20250422150012.png

Pasted image 20250422150023.png

与原有的设计相比，接收方在成功收到一个分组 0 后，其会跳转到等待分组 1 的状态，如果这时传来的是分组 0，接收方就明白这是由于自己发送的 ACK 分组发生了损坏导致发送方重传了旧分组。则接收方会重新发送 ACK 分组，但会直接丢弃收到的分组。

我们发现在上面的设计中，发送方只有当收到了 ACK 分组后才会继续发送下一个分组，而收到 NAK 或是受损分组的效果是一样的，都是重传，我们可以利用这一点省去 NAK。具体而言，我们对 ACK 也进行编号，当发送方发送了分组 $i$ 并等待接收方反馈时，只有当收到 ACK- $i$ 分组时，发送方才会继续发送第 $i + 1$ 个分组。而在接收方，如果收到了破损的分组，发送的不再是 NAK，而是 ACK- $(i - 1)$ 。刚刚提到过，只有当发送方接收到具有对应序号的 ACK 时，才认为接收方接收到了数据并并发送下一个分组，因此在这里 ACK- $(i - 1)$ 发挥了与 NAK 相同的效果。我们会在下面的流水线传输中看到这样做的好处。

此设计下双方的 FSM 片段如下，未给出的部分与上面的图保持一致：

Pasted image 20250422151703.png

Step 3. 经具有丢包和 bit 差错信道的传输

为了防止发送方发送的分组在传输过程中丢失导致接收方没有做出回应，进而陷入死锁。发送方需要进一步实现 超时重传机制。具体而言，发送方在发送一个分组后，会根据先前分组往返所需时间设置一个超时倒计时器，一旦该倒计时器归零仍然没有得到来自接收方的回复，发送方就会认为发生了分组丢失，重传该分组并重置倒计时。

然而存在一种可能，该分组完整传输到了接收方，接收方发送的反馈分组也能够正常到达发送方，只是传输的用时发生了波动。这将导致信道中存在冗余的分组。然而，上面的设计已经能够识别冗余的分组，因此我们可以放心采用该设计。然而，如果超时定时器设置的时间不合理的短，虽然该系统仍然能够正常工作，但是发送方可能会发送多个冗余分组，导致传送效率降低。

双方的 FSM 如下：

Pasted image 20250422152432.png

Step 4. 流水线式传输

到此，我们得到的一直是一个停等协议。在今天的互联网环境下，停等协议存在严重的性能问题，而这来源于它对信道的利用率非常低。由于只有当发送方发送分组并接收到接收方的反馈分组后才会发送下一个分组，受制于传播时延，在一个来回的过程中信道上只有寥寥几个分组在传输，信道的大部分区域是空闲的。

采用流水线式传输可以提高信道利用率，在这种情况下，发送方会不停发送新的未经确认的分组，接收方也会时刻接收到新的分组并返回反馈报文。

为了实现流水线式传输，我们需要进一步：

增加序号范围以为每一个未经确认的分组指定一个序号，方便接收方对收到哪个分组进行确认。
发送方与接收方需要缓存更多的分组。发送方需要缓存更多已发送但未经确认的分组，接收方也需要缓存一些分组，见下文选择重传部分。
制定关于序号、缓冲、处理损失、丢包与重传的方法。目前常见的方法有 回退 N 步（Go-Back-N，GBN） 与 选择重传（Selective Repeat，SR） 两种。

停等协议、回退 N 步与选择重传本质上都是一种 滑动窗口（Sliding Window） 协议。其核心思想是，发送方维护一个 发送缓冲区，在缓冲区中的分组可以直接被发送出去。因此缓冲区中的分组分为三种：未发送的分组、已发送但未确认的分组、已发送已确认的分组。前两者构成了缓冲区中的 发送窗口，其不大于发送缓冲区的大小。发送窗口初始为空，发送方每发送一个新的未确认分组，窗口的前沿向前移动；每当序号最低的分组被接收方确认，窗口的后延向前移动。接收方同样维护一个 接收缓冲区，其等同于 接收窗口，负责指明 接收方会接收哪些分组。超出接收窗口范围的分组将被视作乱序分组丢弃。只有当窗口内 最低序号 的分组被确认接收后，接收窗口才会向前滑动。当高序号分组高于低序号分组到来时，接收方缓存该分组，但不向上交付，窗口也不滑动。

根据发送窗口与接收窗口的大小，我们可以对上面提到的三种协议进行归纳：

协议	发送窗口大小	接收窗口大小
停等协议	$1$	$1$
回退 N 步	$> 1$	$1$
选择重传	$> 1$	$> 1$

回退 N 步

由于在回退 N 步协议中，接收窗口的大小为 1，这限制了接收方只能 顺序接收 分组。所有提前到来的分组都将被视作乱序分组并抛弃，并向发送方发送 所有已确认分组中序号最高分组的 ACK。由于接收方只能顺序接收分组，这隐含了 累积确认 的方式，即对分组 $i$ 的确认表明接收方已经成功接收到分组 $i$ 及前面的所有分组。

在发送方，一旦某个分组太长时间没有得到确认就会触发超时，发送方会重传窗口内所有已发送但未确认的分组。

如果上层在发送窗口已满的情况下向下交付数据，发送方会通过诸如退回该数据、缓存但不放进窗口、使用同步机制指示上层窗口已满等方式拒绝该数据。

下图给出了一个典型的回退 N 步协议的交互过程：

Pasted image 20250423102712.png

选择重传

回退 N 步协议虽然实现了流水线式传输，但仍然不够高效。尤其是当信道出错概率较大时，由于回退 N 步协议中一旦某个低序号分组出错，所有已经正确交付的高序号分组都会被接收方丢弃，信道中可能会充斥大量本无需重传的分组。

选择重传协议通过使接收窗口的大小大于 1 避免了不必要的重传。此时对于分组的确认不再是累积确认而是单独确认。接收方每当收到一个特定的分组，便会缓存该分组并对该特定的分组发送确认。但只有当接收到窗口中序号最低的分组时，接收窗口才会向前滑动，接收方会按照窗口滑动过的分组序号按序把接收到的分组交付给上层。如此使接收方能够缓存乱序的分组。

而在接收方，与回退 N 步不同的是，接收方需要为窗口内的 每一个已发送未确认分组 设置一个超时定时器，当某个特定分组的定时器超时后，只重传该特定的分组。与接收方类似，只有当收到序号最低的分组的确认后，窗口后延才能向前滑动。

这里需要注意的是接收方会为一定范围内 超出窗口 的已接收分组发送确认，这是因为发送方与接收方对于哪些分组已经被接收并不一定有着一样的结果。因此当接收方接收到一个已经超出窗口的已确认分组时，很有可能是因为发送方还没有收到针对该分组的确认而重发了该分组。因此如果对该分组不予理会，发送窗口可能会停在该分组而无法向前滑动。

下图给出了一个典型的选择重传协议的交互过程：

Pasted image 20250423102727.png

一般而言，对于出错率低的信道，比较适合使用 GBN；而对于链路容量大，但延迟也比较大的信道（例如当代互联网的链路就呈现这种特征），适合使用 SR。

此外，由于序号范围有限，发送窗口与接收窗口间如果出现了严重的不同步，将会出现一些严重的故障，这些故障产生的原因与滑动窗口的最大大小有关，考虑下面的例子：

Pasted image 20250423102753.png

显然由于窗口大小太大，很有可能出现分组序号恰好一致但实际发送的分组不同的情况，这会造成严重的后果。为了防止该问题，需要对窗口的最大大小作出规定。假设我们为序号分配 $N$ bit，则一个基本的想法是保证 $发送窗口大小 + 接收窗口大小 \leq 2^{N}$ 。因此，在 GSN 中，窗口大小不能超过 $2^{N} - 1$ ，而在 SR 中，窗口大小不能超过 $2^{N - 1}$ 。